Avoid O(n²) walking of string arrays
authorEmmanuele Bassi <ebassi@gnome.org>
Thu, 16 Jul 2015 15:12:35 +0000 (16:12 +0100)
committerEmmanuele Bassi <ebassi@gnome.org>
Thu, 16 Jul 2015 15:19:55 +0000 (16:19 +0100)
commite259b2f30d86fdde7dab27a25e8088d36421acc7
tree7c3499bb6a4f9ecf237fe64cdc9f53efacc67c78
parent3b41daca780e9e83d04dcad43e2fbd5a2ab8c120
Avoid O(n²) walking of string arrays

"Yo, we heard you like traversing NULL-terminated arrays to operate on
them, so we called g_strv_length() as the for condition, so you can
iterate the array while iterating the array."

Instead of making famed rapper and television producer Xzibit proud, we
should avoid calling g_strv_length() on an array while looping on the
array, to avoid quadratic complexity.

We do this in various places that deal with arrays of strings that we
cannot really guess are short enough not to matter — e.g. the list of
CSS selectors in the inspector, or the required authentication
information for printing.
gtk/gtkprintbackend.c
gtk/inspector/selector.c
modules/printbackends/cups/gtkcupssecretsutils.c
testsuite/a11y/state/state-record.c